package de.uniLuebeck.tcs.algorithmics;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.Writer;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
 * General backbone for backtracking algorithms. This class offers a default
 * backtracking routine that calls other abstract methods. Implement these
 * abstract methods according to your problem setting.
 * 
 * @author Andrea Papst
 * 
 * @param <SolutionType>
 *            The type of a single element of a solution.
 * @param <InstanceType>
 *            The type that represents one problem instance.
 */
public abstract class BacktrackingSkeletton<SolutionType, InstanceType> {

	/**
	 * The value of the current optimal solution.
	 */
	protected double vOpt;
	/**
	 * The current optimal solution.
	 */
	protected List<SolutionType> xOpt;
	/**
	 * This flag is set to true if the solving procedure should be aborted.
	 */
	protected boolean interrupted = false;

	/**
	 * For the given instance of a problem find the optimal solution that starts
	 * with the given intermediate solution of length l by backtracking. The
	 * optimal solution and its value are stored in the (global) variables vOpt
	 * and xOpt.
	 * 
	 * @param l
	 *            backtracking recursion depth
	 * @param x
	 *            intermediate solution
	 * @param instance
	 *            the instance
	 */
	public final void boundedBacktrack(int l, ArrayList<SolutionType> x,
			InstanceType instance) {
		if (isFeasibleSolution(l, x, instance)) {
			double tmpValue = getValue(l, x, instance);
			if (tmpValue > this.vOpt) {
				this.vOpt = tmpValue;
				this.xOpt = (List<SolutionType>) x.clone();
			}
		}
		Iterator<SolutionType> extensions = computeExtensions(l, x, instance);
		while (!interrupted && extensions.hasNext()) {
			x.add(extensions.next());
			boundedBacktrack(l + 1, x, instance);
			x.remove(l);
		}
	}

	/**
	 * Read one problem instance from the input stream, solve it and write the
	 * optimal solution to the output destination.
	 * 
	 * @param in
	 *            Source to read the instance from.
	 * @param out
	 *            Target to write the solution to.
	 * @throws IOException
	 *             in case of an error during reading of instance or writing
	 *             solution
	 */
	public final void solveProblem(BufferedReader in, Writer out)
			throws IOException {
		InstanceType instance;
		instance = readNewInstance(in);
		vOpt = Double.MIN_VALUE;
		xOpt = null;
		boundedBacktrack(0, new ArrayList<SolutionType>(), instance);
		printSolution(out, instance);
	}

	/**
	 * Checks whether the given solution x is valid in the given instance, i.e.
	 * if it fulfills the given problem instance.
	 * 
	 * @param l
	 *            backtracking recursion depth
	 * @param x
	 *            intermediate solution
	 * @param instance
	 *            the instance
	 * @return Returns true if the solution is valid.
	 */
	protected abstract boolean isFeasibleSolution(int l, List<SolutionType> x,
			InstanceType instance);

	/**
	 * Computes the value of the given feasible solution.
	 * 
	 * @param l
	 *            backtracking recursion depth
	 * @param x
	 *            feasible solution
	 * @param instance
	 *            the instance
	 * @return Returns the value for the given solution.
	 */
	protected abstract double getValue(int l, List<SolutionType> x,
			InstanceType instance);

	/**
	 * Determine possible extensions to the given intermediate solution x. The
	 * extensions are checked in the order they are traversed by the returned
	 * iterator.
	 * 
	 * @param l
	 *            backtracking recursion depth
	 * @param x
	 *            intermediate solution
	 * @param instance
	 *            the instance
	 * @return Returns an Iterator over all possible extensions.
	 */
	protected abstract Iterator<SolutionType> computeExtensions(int l,
			List<SolutionType> x, InstanceType instance);

	/**
	 * Read a new problem instance from the input stream.
	 * 
	 * @param reader
	 *            Reader to read the instance from.
	 * @return Returns a new problem instance.
	 * @throws IOException
	 *             in case of an error while reading from reader
	 */
	protected abstract InstanceType readNewInstance(BufferedReader reader)
			throws IOException;

	/**
	 * Prints the optimal solution xOpt into the given StringBuffer.
	 * 
	 * @param output
	 *            solution is printed there.
	 * @param instance
	 *            the instance
	 * @throws IOException
	 *             in case of an error while writing to output
	 */
	public abstract void printSolution(Writer output, InstanceType instance)
			throws IOException;

	/**
	 * Returns the names of the authors of the class
	 * 
	 * @return names of the authors
	 */
	public String getAuthor() {
		// Please overwrite this method and return your names.
		return "Andrea Papst + Lennart Sauerbeck + Andreas Jakoby";
	}

	/**
	 * Set the interrupted flag to abort the backtracking recursion.
	 */
	public void setInterrupted() {
		this.interrupted = true;
	}

}
